/**
 * [39] 组合总和
 * 思路：
 * [2,3,6,7] 7
 * 2 2 2
 * 2 2 3
 *
 * @format
 * @lc app=leetcode.cn id=39 lang=javascript
 */

// @lc code=start
/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
// 递归算法
var combinationSum = function (candidates, target) {
    // candidates.sort((a, b) => a - b)
    const result = []
    let rest = 0
    for (let i = 0; i < candidates.length; i++) {
        rest = target - candidates[i]
        if (rest == 0) result.push([candidates[i]])
        else if (rest > 0) {
            combinationSum(candidates.slice(i), rest).forEach((e) => {
                e.push(candidates[i])
                result.push(e)
            })
        }
    }
    return result
}
// debugger
// const candidates = [2, 3, 6, 7]
// const target = 7
// const result = combinationSum(candidates, target)
// console.log(result)
// @lc code=end
// 排序
// Accepted
// 160/160 cases passed (63 ms)
// Your runtime beats 98.3 % of javascript submissions
// Your memory usage beats 5 % of javascript submissions (58.3 MB)
// 不排序
// Accepted
// 160/160 cases passed (69 ms)
// Your runtime beats 87.69 % of javascript submissions
// Your memory usage beats 5 % of javascript submissions (57.2 MB)
